Міністерство освіти і науки, молоді та спорту України Національний університет „ Львівська політехніка ” ІКТАМ Кафедра ЕОМ
Курсова робота з предмету: “ Паралельні та розподілені обчислення ” на тему: “ Паралельне виконання операцій множення матриць ” Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністю N1 * N2) на матрицю В (розмірністю N2 * N3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, які наведені нижче. Визначення вхідних даних: n1 = 120 n2=56 n3=67 5b-12b-6b-11b-8b-1b-3b-13b , де «nb»- номер букви П.І.Б. РАОПНЗДВ=> 93,27,250,219,134,67,13,203 9310 = 5D16 2710 = 1B16 25010 = FA16 21910 = DB16  13410 = 8616 6710 = 4316 132 = D16 20310 = CD16   Матриця зв’язків орієнтованого графу: №проц. 1 2 3 4 5 6 7 8  1 0 1  0 1 1 1 0 1  2 0 0 1 1 1 0 1 1  3 1 1 0 1 1 0 1 0  4 1 1 0 0 1 0 1 1  5 1 0 0 0 0 1 1 0  6 0 1 0 0 0 0 1 1  7 0 0 0 0 1 1 0 1  8 1 1 0 0 1 0 1 0  Визначення початкового завантаження: Номер – 0909624
– спільна пам’ять. Співвідношення часових параметрів:
, де Zi – відповідна цифра номера залікової книжки, k – кількість цифр в номері залікової книжки.
tU – час виконання однієї операції множення; tS – час виконання однієї операції сумування; tP – час виконання однієї операції пересилання даних між процесорами; tZ – час виконання операції завантаження одних даних; tW – час виконання операції вивантаження одних даних. Анотація Дана курсова робота представляє собою розробку алгоритму паралельного перемноження двох матриць розміром A(120*56) та В(56*67) на восьми процесорах використовуючи кільцеву структуру зі спільною пам’яттю. У звіті наведені функціональна схема, блок-схема виконання алгоритму, проведений розрахунок часових характеристик алгоритму, відповідно до яких визначено ефективність його виконання відносно послідовного. Програма написана засобами мови C++ з використанням бібліотеки MPI. Зміст Вступ 6 1. Теоретичний розділ 7 2. Розробка блок-схеми виконання алгоритму 9 3. Розробка функціональної схеми 10 4. Розрахунковий розділ 12 5. Розробка програми 14 Висновки 16 Список літератури 17 Додаток А. Лістинг програми 18 Вступ Паралельні обчислювальні системи - комп'ютерні системи, що реалізовують тим або іншим способом паралельну обробку даних на багатьох обчислювальних вузлах для підвищення загальної швидкості розрахунку. Ідея розпаралелення обчислень базується на тому, що більшість завдань можуть бути розділені на набір менших завдань, які можуть бути вирішені одночасно. Зазвичай паралельні обчислення вимагають координації дій. Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора має фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму. Розподілені обчислення - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу. Розподілені обчислення є окремим випадком паралельних обчислень, тобто одночасного розв'язання різних частин одного обчислювального завдання декількома процесорами одного або кількох комп'ютерів. Тому необхідно, щоб завдання, що розв'язується було сегментоване — розділене на підзадачі, що можуть обчислюватися паралельно. При цьому для розподілених обчислень доводиться також враховувати...